翻訳と辞書 Words near each other ・ Fermín Emilio Lafitte ・ Fermín Francisco de Carvajal-Vargas ・ Fermín Jáudenes ・ Fermín Lasuén ・ Fermín Martín Piera ・ Fermat curve ・ Fermat number ・ Fermat point ・ Fermat polygonal number theorem ・ Fermat primality test ・ Fermat Prize ・ Fermat pseudoprime ・ Fermat quintic threefold ・ Fermat quotient ・ FermaT Transformation System ・ Fermat's factorization method ・ Fermat's Last Theorem ・ Fermat's Last Theorem (book) ・ Fermat's Last Theorem in fiction ・ Fermat's little theorem ・ Fermat's principle ・ Fermat's right triangle theorem ・ Fermat's Room ・ Fermat's spiral ・ Fermat's theorem ・ Fermat's theorem (stationary points) ・ Fermat's theorem on sums of two squares ・ Fermata ・ Fermata Arts Foundation ・ Fermatta Music Academy Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fermat's factorization method ： ウィキペディア英語版 Fermat's factorization method Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: :$N\; =\; a^2\; -\; b^2.$ That difference is algebraically factorable as $(a+b)(a-b)$; if neither factor equals one, it is a proper factorization of ''N''. Each odd number has such a representation. Indeed, if $N=cd$ is a factorization of ''N'', then :$N\; =\; \backslash left(\backslash frac\backslash right)^2\; -\; \backslash left(\backslash frac\backslash right)^2$ Since ''N'' is odd, then ''c'' and ''d'' are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let ''c'' and ''d'' be even.) In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either. ==Basic method== One tries various values of ''a'', hoping that $a^2-N\; =\; b^2$, a square. :FermatFactor(N): // N should be odd :: a ← ceil(sqrt(N)) :: b2 ← a *a - N :: while b2 isn't a square: :::: a ← a + 1 // equivalently: b2 ← b2 + 2 *a + 1 :::: b2 ← a *a - N // a ← a + 1 :: endwhile :: return a - sqrt(b2) // or a + sqrt(b2) For example, to factor $N\; =\; 5959$, the first try for ''a'' is the square root of $5959$ rounded up to the next integer, which is $78$. Then, $b^2\; =\; 78^2-5959\; =\; 125$. Since 125 is not a square, a second try is made by increasing the value of ''a'' by 1. The second attempt also fails, because 282 is again not a square. The third try produces the perfect square of 441. So, $a\; =\; 80$, $b\; =\; 21$, and the factors of $5959$ are $a\; -\; b\; =\; 59$ and $a\; +\; b\; =\; 101$. Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of ''a'' and ''b''. That is, $a\; +\; b$ is the smallest factor ≥ the square-root of ''N'', and so $a\; -\; b\; =\; N/(a\; +\; b)$ is the largest factor ≤ root-''N''. If the procedure finds $N=1\; \backslash cdot\; N$, that shows that ''N'' is prime. For $N\; =\; cd$, let ''c'' be the largest subroot factor. $a\; =\; (c+d)/2$, so the number of steps is approximately $(c\; +\; d)/2\; -\; \backslash sqrt\; N\; =\; (\backslash sqrt\; d\; -\; \backslash sqrt\; c)^2\; /\; 2\; =\; (\backslash sqrt\; N\; -\; c)^2\; /\; 2c$. If ''N'' is prime (so that $d\; =\; 1$), one needs $O(N)$ steps. This is a bad way to prove primality. But if ''N'' has a factor close to its square root, the method works quickly. More precisely, if ''c'' differs less than $^$ from $\backslash sqrt\; N$, the method requires only one step; this is independent of the size of ''N''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fermat's factorization method」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.